模拟赛题解/2025.8.25 模拟赛

T1-字符串排序（sort）

题面

给出 $n$ 个仅包含大写字母的字符串 $s_1,s_2,\cdots,s_n$。

对于每次操作，可以选择任意一个字符串，将其内部的字符任意重排，记进行完重排后的字符串为 $s_1',s_2',\cdots,s_n'$。

字符串 $s$ 的字典序小于字符串 $t$，当且仅当存在一个正整数 $1\leq i\leq min(|s|,|t|)$，满足 $s_1\sim s_{i-1}$ 和 $t_1\sim t_{i-1}$ 相同，且 $s_i<t_i$，或 $s$ 和 $t_1\sim t_{|s|}$ 相同且 $|s|<|t|$。

求出是否存在一个方案使得对于任意 $1\leq i\leq n-1$，$s_i'<s_{i+1}'$。

若存在，请求出一种方案。

$1\leq T\leq10,2\leq n\leq100,1\leq|s|\leq100$。

题解

首先有一个很直接的贪心思路：从左到右考虑所有字符串，重排它使得它在字典序 $\geq$ 前一个字符串的情况下，最小化其字典序（即留给后面的字符串更大的操作空间）。

考虑模拟这个思路，对于每个字符串尝试从左到右逐位确定某一个位置最小能填什么：从小到大枚举该位置上的字符，并检查在这一位填入该字符是否满足条件（即这个位后面的剩余字符从大到小填，能否使当前字符串字典序 $\geq$ 前一个字符串）。

复杂度 $O(T\sum|S|)$。

T2-表白（love）

题面

有 $n$ 个数 $w_1,w_2,\cdots,w_n$。

给出区间 $[l,r]$，要求在 $w_l\sim w_r$ 中选择若干个数，满足其乘积对 $m$ 取模的值最大。

对于每一个询问，求出得到的最大值。

$1\leq T\leq6,1\leq n,q\leq10^5,1\leq m\leq521,1\leq w_i\leq10^9,1\leq l_i\leq r_i\leq n$。

题解

首先考虑 $O(n^2m)$

定义 $f_{i,j,k}$ 表示 $[i,j]$ 区间，能不能凑出 $k$，转移是平凡的。

考虑优化掉一个 $n$，dp 状态的结果只有 $0/1$ 太浪费了，重新定义 $f_{i,j}=x$ 表示最大的 $x$ 满足只使用 $[x,i]$ 的元素能凑出 $j$ 。

特别的，当 $[1,i]$ 都不能凑出 $j$ 时 $f_{i,j}=0$。

对于每一个询问，考虑枚举答案，即最大的满足 $f_{r,i}\geq l$ 的 $i$。

复杂度 $O((n+q)m)$。

T3-树上棋盘（tree）

题面

有一棵有 $2n$ 个节点的树，树上每个节点有一个权值 $a_i$，$1\leq a_i\leq n$，保证每个权值都恰好出现 $2$ 次。

定义得分为树上满足以下条件的节点二元组 $(u,v)$ 的数量：

• $u,v$ 之间有边直接相连；
• $a_u=a_v$。

可以进行若干次交换操作，每次操作可以选择两个节点并交换它们的权值，每个点上的权值最多经历一次交换。

求能够达到的最大得分和对应的交换方案。

$1\leq n\leq5\times10^5,1\leq a_i\leq n,1\leq u,v\leq 2n$，$2n-1$ 条边构成一棵树。

题解

使用贪心或者 DP 求解一个树上的最大匹配 $M={(u_1,v_1),(u_2,v_2),\cdots,(u_k,v_k)}$，则答案不会超过 $k$。

大胆猜测答案一定可以取到 $k$（到这里已经可以获得第一问的 $20$ 分），以下是构造方法：

对于上面的最大匹配 $M$，构造一个有 $n$ 个结点的无向图 $G$，连边 $a_{u_i}\leftrightarrow a_{v_i}(1\leq i\leq k)$。

由于原树上每个结点在最大匹配中最多出现一次，而 $a_i$ 在 $a$ 中恰好出现两次，所以该图中结点度数不超过 $2$。

我们先引入一个叫做“缩二度点”的操作：假设在 $G$ 中，对于结点 $x$ 有边 $x\leftrightarrow y$ 和 $x\leftrightarrow z$，那么意味着在最大匹配中有两条边满足 $a_{u_i}=x,a_{v_i}=y$ 和 $a_{u_j}=x,a_{v,j}=z$；

此时交换 $u_j,v_j$，即可以将匹配中的边调整为 $a_{u_i}=a_{v_i}=x$ 和 $a_{u_j}=y,a_{v_j}=z$。——对应到 $G$ 中，相当于删除了边 $x\leftrightarrow y$ 和 $x\leftrightarrow z$（$x$ 直接满足条件，可以不管了），加入了一条新边 ，十分类似广义串并联图中的“缩二度点”操作。

考察 $G$ 的性质，由于结点度数不超过 $2$，所以 $G$ 中的每个连通块要么是一个环，要么是一条链：

使用上面的“缩二度点”操作，一个环可以被缩成一个单点（即环上所有结点全部调整完毕），而一条链最后必然被缩成 $x\leftrightarrow y$ 的形态：思考造成这种现象的本质，由于这两个结点度数都为 $1$，那么满足 $a_i=x$ 的某个 $i$ 必然没有被选入最大匹配中。

此时只需要将 $y$ 在匹配中对应的结点和那个没被选入的 $i$ 交换即可。

根据不同实现，时间复杂度为 $O(n\log n)$ 或 $O(n)$。

T4-橡子 5（acorn）

题面

有一棵有 $n$ 个节点的树，节点编号为 $1\sim n$，给定常数 $k$。

对于一个节点 $s$，定义 $f(s)$ 为：

• 以结点 $s$ 为根，并据此将树的边定向使其成为一棵叶向树：具体地，若在以 $s$ 为根的情况下，$u$ 为 $v$ 的父亲，那么边 $(u,v)$ 被定向为 $u\rightarrow v$。接下来可以添加 $k$ 条从 $s$ 出发的有向边，终点任意。令 $d_u$ 表示 $s$ 到 $u$ 的最短路，答案为所有加边方案中 $\displaystyle\max_{u=1}^nd_u$ 的最小值。

在某些测试点中，只需要对于 $s=1$ 求出 $f(s)$；而在另一些测试点中，需要对于 $s=1,2,\cdots,n$ 均求出 $f(s)$。

$1\leq T\leq5,2\leq n\leq2\times10^5,1\leq k\leq n-1,nk\leq2\times10^5,0\leq t\leq1,1\leq u_i,v_i\leq n$，输入数据保证形成一棵树。

题解

首先考虑如何判断一个答案是否可行。

设我们现在判断答案为 $x$ 是否合法，我们可以从下往上做，每次将最深的点拿出来，此时的操作应该是其 $x-1$ 级祖先向根节点连边，这样这一整颗子树都是合法的，删掉这个子树。

重复上述过程 $k$ 次后判最深的点是否和根的距离小于等于 $x$，即为 $x$ 是否合法。

将这棵树拍到 DFS 序上，用线段树维护最深的点，删子树可以变成一个区间减 $\infty$。这一部分的时间复杂度为 $O(k\log n)$。

考虑换根怎么做。首先线段树上维护的是每个点到深度的距离，设当前的根为 $u$，换根后为 $v$，只需要将 $v$ 子树内到根的距离减一， 子树外到根的距离加一，这个也是容易维护的。 接下来就剩下树上 $k$ 级祖先和换根后的子树，这个比较经典，分讨就可以了。

具体的，以 $rt$ 为根，$u$ 的树上 $k$ 级祖先可以如下分讨（记 $u$ 和 $rt$ 在原树上的 lca 为 $l$）：

1. 若 $dis(u,l)\geq k$，则 $u$ 的树上 $k$ 级祖先为原树上的 $k$ 级祖先；
2. 否则，则 $u$ 的树上 $k$ 级祖先为原树上 $rt$ 的 $dis(u,rt)-k$ 级祖先。

以 $rt$ 为根，$u$ 的子树为：

1. $rt=u$，此时 $u$ 的子树为所有点；
2. 原树中，$rt$ 在 $u$ 的子树内，设 $v$ 为 $rt\rightarrow u$ 路径上倒数第二个点，此时 $u$ 的子树为除原树中 $v$ 的子树以外的所有点；
3. 否则，$u$ 的子树不变。

对于每个点都二分一下可以做到 $O(nk\log^2n)$，精细实现可以通过。

但是还可以做到更优。发现换根后答案的变动不会超过 $1$，可以将 $O(\log n)$ 次判断缩到 $O(1)$ 次。

此时时间复杂度为 $O(nk\log n)$。